#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        map<int,string> mpLetter = {{0,""},
                                    {1,""},
                                    {2,"abc"},
                                    {3,"def"},
                                    {4,"ghi"},
                                    {5,"jkl"},
                                    {6,"mno"},
                                    {7,"pqrs"},
                                    {8,"tuv"},
                                    {9,"wxyz"},};
        queue<string> quDigit;
        for(auto c : mpLetter[digits[0]-'0']) {
            quDigit.push(string() + c);
        }
        for(int i=1; i<digits.length(); i++) {
            int nCnt = quDigit.size();
            for(int j=0; j<nCnt; j++){
                string tmp = quDigit.front(); quDigit.pop();
                for (auto c:mpLetter[digits[i]-'0']){
                    quDigit.push(tmp+c);
                }
            }
        }
        vector<string> ans;
        while(!quDigit.empty()) {
            ans.push_back(quDigit.front());
            quDigit.pop();
        }
        return ans;
    }
};
